package leetcode.editor.cn;

/**
 * @id: 96
 * @title: 不同的二叉搜索树
 */
 
//给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 
//
// 示例: 
//
// 输入: 3
//输出: 5
//解释:
//给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
//
//   1         3     3      2      1
//    \       /     /      / \      \
//     3     2     1      1   3      2
//    /     /       \                 \
//   2     1         2                 3 
// Related Topics 树 动态规划 
// 👍 1105 👎 0

public class P96UniqueBinarySearchTrees {
    public static void main(String[] args) {
        Solution solution = new P96UniqueBinarySearchTrees().new Solution();
        // todo
        int result = solution.numTrees(5);
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int[] tables;
    public int numTrees(int n) {
        tables = new int[n+1];
        tables[0] = tables[1] = 1;
        return catalanNumberPd(n);
    }

    public int catalanNumberPd(int n) {
        if (tables[n] >= 1) return tables[n];
        tables[n] = 0;
        for (int i = 1 ; i <= n ; i++)
            tables[n] += catalanNumberPd(i-1) * catalanNumberPd(n-i);
        return tables[n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}